\documentclass[12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{amsfonts}
\usepackage{algorithm2e}
\usepackage{listings}

\lstset{ %
			language=Python,
			basicstyle=\scriptsize,
			numbers=left,
			stepnumber=1,
			numbersep=4pt,
			tabsize=2,
}


\title{Problema de selecci\'on de proyectos}
\author{
        Ignacio Garay \\
                \and
        Ariel Liguori\\
        	\and
	Pablo Musumeci
}
\date{\today}



\begin{document}
\maketitle

\begin{abstract}
El presente es un an\'alisis sobre el problema de  selecci\'on de proyectos, el
cual se modelizará a través de una red de transporte, y se resolverá obteniendo
el flujo máximo y las aristas utilizadas para obtener dicho flujo en la red que
caracteriza al problema.
\end{abstract}

\newpage
\tableofcontents
\newpage

\section{Introducci\'on}\label{intro}
En el problema selecci\'on de proyectos se denotan 2 tipos de actores:
\begin{description}
	\item[Proyectos] Los mismos requieren de la disponibilidad de 
	cierto tipo de profesionales para la realización de la tarea.
	Son los que aportan el flujo entrante de dinero a la empresa.
	\item[Profesionales] Son aquellos que hacen posible la realización
	de los trabajos en las diferentes áreas. Pueden trabajar en más de un
	proyecto a la vez. Su costo de contratación representa un egreso
	de dinero para la empresa.
\end{description}

El problema reside en encontrar que profesionales contratar, y que proyectos
aceptar para maximizar las ganancias netas, las cuales son los beneficios obtenidos
por la realización de los proyectos menos los costos necesarios que se afrontaron
para contratar a los profesionales que trabajaron en los mismos.

\vspace{0.5cm}
Se debe tener en cuenta que cada profesional puede desempeñar tareas en una o varias
áreas de interés, con lo cual, su contratación puede ser de utilidad para más de un
trabajo en particular, ya que puede colaborar en varios de ellos de manera simultánea.
Para llevar a cabo un proyecto, se requiere que la totalidad de las áreas que el mismo
abarca esten cubiertas por algún profesional que tenga conocimientos en la misma.

Es decir, existen una serie de \emph{dependencias} que se deben cumplir para poder
realizar un trabajo en particular, y las mismas son que las áreas relacionadas con
el trabajo deben estar cubiertas por un profesional como mínimo.

\newpage
\section{Definiciones}
Antes de realizar el planteo matemático del problema a tratar, daremos algunas
definiciones que serán utilizadas en el mismo y creemos que es beneficioso
tener al alcance a la hora de explicar el mismo.

\begin{description}
	\item[Red de transporte] Sea $N = (V,E)$ un grafo dirigido conexo sin lazos. 
	Entonces $N$ es una red de transporte si se cumplen las condiciones:
	
    \begin {itemize}

        \item Existe un único vértice $a \in V$ tal que el grado de entrada
	de $a$ es igual a $0$. Dicho vértice es la \emph{fuente}.
 
        \item Existe un único vértice $z \in V$ tal que el grado de salida
        de $z$ es igual a $0$. Dicho vértice se denomina \emph{sumidero}.

        \item El grafo $N$ es ponderado, por lo que existe una función $E$
        en el conjunto de los enteros no negativos que asigna a cada arista 
        $e = (v,w) \in E$ una \emph{capacidad}, que se denota como $c(e) = c(v,w)$.
		
	\end{itemize}

	\item[Flujo] Si $N = (V,E)$ es una red de transporte, una función $f$ de $E$
        a los enteros no negativos es un flujo de $N$ si
        \begin{itemize}
          \item $f(e) \le c(e)$ para toda arista $e \in E$.

          \item Para cualquier $v,w \in V$ distinto de la fuente o del sumidero, 
          $\sum f(w,v) = \sum f(v,w)$.
        \end{itemize}

        La primer condición especifica que la cantidad de material transportado
        a lo largo de una arista no puede exceder su capacidad. La segunda condición
        pide que la cantidad de material que fluye hacia un vértice $v$ debe ser igual
        a la cantidad que fluye desde ese vértice. Esto vale para todos los vértices
        exceptuando a la fuente y al sumidero.

        El valor de un flujo esta dado por:

        $val(f) = \sum f(x,v) - \sum f(w,x)$ con $x \in P$ y $w,v \in \overline{P}$

        \item[Saturación] Una arista esta saturada si $f(e) = c(e)$. Es decir, 
        transporta material al límite máximo posible de su capacidad.

        \item[Conservación del flujo] El flujo total que sale de la fuente $a$ es
        igual al flujo total que llega al sumidero $z$.

        \textbf{Demostración} Considerando a $P = \{a\}$ y $\overline{P} = V - P$
        sabemos que $val(f) = \sum f(x,v) - \sum f(w,x)$ con $x \in P$ y $v,x \in \overline{P}$.
        
        $ \sum f(w,x) = 0 = \sum f(w,a)$ ya que el grado de entrada de $a$ es 0.

        Analogamente $ \sum f(z,w) = 0$ ya que el grado de salida de $z$ es 0.

        Por lo tanto $val(f) = \sum f(a,v) = \sum f(y,z)$ con $y \in V - \{z\}$ y $v \in V - \{a\}$. 

        \item[Corte] Si $N = (V,E)$ es una red de transporte, y $C$ es un conjunto de
        corte para el grafo no dirigido asociado a $N$ si la eliminación de las aristas
        de $C$ de la red, produce la separación de la fuente con el sumidero.

        La capacidad de un corte se define como $\sum c(v,w)$ con $v \in P$ y $w \in \overline{P}$.
        Siendo $P$ y $\overline{P}$ los 2 conjuntos separados por el corte.

        \item[Teorema del flujo máximo y el corte mínimo] Para una red de transporte $N = (V,E)$
        el flujo máximo que se puede obtener en $N$ es igual a la capacidad mínima sobre todos
        los cortes de la red.
\end{description}

\newpage
\section{Planteo}\label{planteo}
El planteo matem\'atico del problema es el siguiente:

Se cuenta con un conjunto $P$ de proyectos que \emph{no} son seleccionados, y un
conjunto $Q$ con los profesionales que fueron contratados. Cada proyecto $p_i$ tiene
un beneficio de $r(p_i)$ y cada profesional $q_j$ tiene un costo de contratación 
asociado de $c(q_j)$.

El problema puede verse como un problema de maximización, en donde se quiere maximizar
el beneficio obtenido, restando los costos de los profesionales y el beneficio de los
proyectos \emph{no} realizados:

\begin{equation}\label{..}\sum_{i} r(p_i) - \sum_{p_i \in P} r(p_i) - \sum_{q_j \in Q} c(q_j)  \end{equation}

También podría verse como un problema de minimización, en donde lo que se intenta
minimizar es el beneficio que \emph{no} se obtiene (debido a los proyectos que no se realizan)
y el costo de contratación de los profesionales.

\begin{equation}\label{..} \sum_{p_i \in P} r(p_i) + \sum_{q_j \in Q} c(q_j) \end{equation}

El problema de arriba puede resolverse como un problema de \emph{corte mínimimo} en
una red de flujo, en donde el nodo fuente este conectado a los proyectos con capacidad
$r(p_i)$ , el nodo sumidero conectado a los profesionales con capacidad $c(q_j)$. 
Una arista $(p_i, q_j)$ de \emph{capacidad infinita} es agregada al grafo si el 
proyecto $p_i$ requiere del profesional $q_j$ para su realización.

Para encontrar el \emph{flujo máximo} se utilizará el algoritmo de Ford-Fulkerson.
La idea principal del algoritmo consiste en que, mientras exista un camino de la 
fuente hacia el sumidero con capacidad disponible, enviamos flujo a través de todas
las aristas de ese camino. 

\begin{algorithm}[H]

	\SetAlgoLined

	\KwData{Grafo $G$, con capacidad de flujo $c$, un nodo fuente $s$ y un sumidero $t$ }
	\KwResult{Flujo $f$ de $s$ a $t$ }
	$f(u,v)\leftarrow 0\ para\ todas\ las\ aristas(u,v)$\;
	\While{exista un camino $p$ de $s$ a $t$ con capacidad $c_f(u,v) \geq 0$}{
		$Encontrar\ c_f(p) = min(c_f(u,v): (u,v) \in p)$\;
		\For{cada arista $(u,v) \in p$}{
			$f(u,v) \leftarrow f(u,v) + c_f(p)$\;
			$f(v,u) \leftarrow f(v,u) - c_f(p)$\;
		}
	}
\caption{Algoritmo de Ford–Fulkerson}
\end{algorithm}

\newpage

\section{Análisis}\label{analisisdina}
\subsection{Complejidad computacional}
Suponemos para este análisis, que las capacidades de las aristas con las que el
algoritmo va a trabajar son valores del tipo \textbf{enteros}.


\vspace{0.3cm}
Sea $C$ la cantidad de flujo máxima que puede fluir por la red de transporte, se
puede decir que el algoritmo de Ford-Fulkerson termina en como máximo $C$ iteraciones
del ciclo \emph{While}. Esto se debe a que el valor del flujo se va incrementando 
en cada iteración ( en 1 unidad como mínimo debido al tipo de dato con el que trabajamos),
con lo cual, como máximo puede durar $C$ iteraciones.


\vspace{0.3cm}
Sea $V$ el número de vértices, y $E$ el número de aristas en $G$. Asumiendo que
todos los vértices tienen como mínimo una arista incidente ( $\rightarrow E \ge V/2$), 
entonces el algoritmo trabaja en orden de $O(E+V)=O(E)$.


\vspace{0.3cm}
\emph{¿Como saber si el flujo encontrado por el algoritmo es el máximo posible?}

Para garantizar que el resultado del algoritmo de Ford-Fulkerson devuelve el valor
máximo posible del flujo en una red de transporte, se utiliza el teorema de 
\emph{Corte mínimo - Flujo máximo}, el cual asegura que el máximo valor de la 
cantidad de flujo que puede fluir por la red es igual a la capacidad del corte de
mínimo valor.

Un corte $C= (S, T)$ se define como una partición de V tal que $s \in S$ y $t \in T$.
El conjunto de corte es $\{(u,v) \in Aristas | u \in S , v \in T\}$.

La capacidad de un corte $C$ queda definida como 

\begin{equation}\label{..} c (S,T) = \sum_{(u,v) \in S \times T} c_{uv} \end{equation}


\vspace{0.3cm}
Dado un flujo $f$ máximo, podemos encontrar un corte s-t de capacidad mínima en
tiempo O(E). Esto se debe a que construimos el grafo \emph{residual} $G_f$ y realizamos
una busqueda en anchura 
para determinar el conjunto $A$ de vertices que se pueden alcanzar. Luego definimos $B = V - A$
y retornamos el corte $(A,B)$.
\newpage
\bibliographystyle{abbrv}
\bibliography{simple}

\newpage
\section{Anexo: implementaci\'on del algoritmo en Python}\label{codigo}
\subsection{project.py}
\lstinputlisting{project.py}
\newpage
\section{Bibliografía}

\begin{verbatim}
	http://en.wikipedia.org/wiki/Maximum_flow

	http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

	http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

	http://en.wikipedia.org/wiki/Maximum_flow_problem

	Algorithm Desing from Jon Kleinberg and Eva Tardos (Chapter 7 - Network Flow).

\end{verbatim}
\end{document}
